// https://www.lintcode.com/problem/copy-list-with-random-pointer/description

/**
 * Definition for singly-linked list with a random pointer.
 * struct RandomListNode {
 *     int label;
 *     RandomListNode *next, *random;
 *     RandomListNode(int x) : label(x), next(NULL), random(NULL) {}
 * };
 */
class Solution {
public:
    /**
     * @param head: The head of linked list with a random pointer.
     * @return: A new head of a deep copy of the list.
     */
    RandomListNode *copyRandomList(RandomListNode *head) {
        // Memory Limit Exceeded
        // if (!head) return NULL;
        // RandomListNode * new_head = new RandomListNode(head->label);
        // new_head->next = copyRandomList(head->next);
        // new_head->random = copyRandomList(head->random);
        // return new_head;
        
        // 重新构造一条：这个有问题，这个一开始复制的next和random指针指的还是原来链表的值
        // RandomListNode * dummy = new RandomListNode(-1);
        // dummy->next = new RandomListNode(head->label);
        // RandomListNode * result = dummy;
        // while (head)
        // {
        //     RandomListNode * tmp = new RandomListNode(head->label);
        //     // tmp->next = head->next;
        //     tmp->random = head->random;
        //     result->next = tmp;
        //     result = result->next;
        //     head = head->next;
        // }
        // return dummy->next;
        
        
        
        // 法一：用哈希表存random指针
        // map<RandomListNode *, RandomListNode *> old2new;
        // RandomListNode *tmp = head;
        // RandomListNode *dummy = new RandomListNode(-1);
        // dummy->next = head;
        // RandomListNode *curr = dummy;
        // while (tmp)
        // {
        //     // RandomListNode * new_node = tmp;
        //     // Node with label -1 was not copied but a reference to the original one.
        //     // 注意是Return a deep copy of the list.
        //     RandomListNode * new_node = new RandomListNode(tmp->label);
        //     new_node->next = tmp->next;
        //     old2new[tmp] = new_node;
        //     tmp = tmp->next;
        //     curr->next = new_node;
        //     curr = curr->next;
        // }
        // tmp = head;
        // while (tmp)
        // {
        //     old2new[tmp]->random = tmp->random;
        //     tmp = tmp->next;
        // }
        // return dummy->next;
        
        // 法二：O(1) 通过next指针copy节点 1->1`->2->2`->3->3`->4->4`,再拆分
        RandomListNode * p = head;
        while (p)
        {
            RandomListNode * node = new RandomListNode(p->label);
            node->next = p->next;
            node->random = p->random;
            p->next = node;
            p = p->next->next;
        }
        RandomListNode * dummy = new RandomListNode(-1);
        RandomListNode * result = dummy;
        p = head;
        while (p)
        {
            RandomListNode * tmp = p->next;
            p->next = tmp->next;
            result->next = tmp;
            result = result->next;
            p = p->next;
        }
        return dummy->next;
    }
};